package com.leetcode.链表;

//排序链表
public class lc_148 {
    public static void main(String[] args) {

    }

    //给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
    public ListNode sortList(ListNode head){
        //思路:递归 归并 -> 拆分 排序 合并 返回头节点
        //边界条件:无结点或者只有一个节点的时候,直接返回
        if (head == null || head.next == null){
            return head;
        }

        /*
         * 使用快慢指针法找到链表中点：
         * - 快指针每次移动两步，慢指针每次移动一步
         * - 当快指针到达末尾时，慢指针正好在中间位置
         * - 这样可以将链表分为左右两部分
         */
        ListNode fast = head.next; // 快指针从head.next开始，确保偶数节点时中点在前半部分
        ListNode slow = head;      // 慢指针

        while (fast != null && fast.next != null) {
            slow = slow.next;      // 慢指针移动一步
            fast = fast.next.next; // 快指针移动两步
        }

        // 分割链表：将链表从中间断开
        ListNode tmp = slow.next;  // tmp保存右半部分的头节点
        slow.next = null;          // 切断左右两部分连接

        // 递归排序左半部分和右半部分
        ListNode left = sortList(head);   // 排序左半部分（head到slow）
        ListNode right = sortList(tmp);  // 排序右半部分（slow.next到末尾）

        /*
         * 合并两个已排序的链表：
         * - 创建一个虚拟头节点(dummy)作为合并后链表的起始点
         * - 使用指针h遍历合并过程
         */
        ListNode h = new ListNode(0); // 虚拟头节点
        ListNode res = h;             // 保存虚拟头节点引用，用于最后返回结果

        // 当左右两部分都还有节点时，比较大小并连接
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;    // 连接较小的左节点
                left = left.next; // 左链表指针后移
            } else {
                h.next = right;   // 连接较小的右节点
                right = right.next; // 右链表指针后移
            }
            h = h.next;           // 合并链表指针后移
        }

        // 连接剩余部分：将未遍历完的左或右链表直接连接到合并链表末尾
        h.next = left != null ? left : right;

        // 返回排序后的链表（跳过虚拟头节点）
        return res.next;
    }
}
